As demand for practical solutions to larger scale data fusion or data association tasks increases, issues of computational complexity of the algorithmic approaches used become topics of more serious interest. Theoretically well-defined and well-grounded analytical models for data association problems may exist without having easily computed solutions. When such situations arise it is desirable to determine efficient approximation procedures that, if possible, are well-conditioned such that certain bounds on errors can be determined.
When data association tasks consist of merging, or fusing, two or more large sets of data that both represent a common underlying reality or ground truth, such issues of the computational complexity of the algorithms do arise. We assume that a general task of data association is to take two independent sets of state estimates, e.g., measurements and predicted state values, that each represent a common underlying set of objects and to determine the associations between the elements from the distinct sets of data. Fusion, or subsequent assignment of the elements from the independent representations to a single representation will depend on the determination of these associations.
Typically in discussions of computational complexity, reference is made to the underlying graph theoretic structure of the problem at hand. The purpose of this exercise is to determine if the general problem has ever arisen in other applications. In fact, this is indeed the case with some data association problems. The graph structure associated with the fusion problem is a bipartite graph, since by assumption there are two sets of data, independently arrived at. From each element a.epsilon.A there may be an association with an element b.epsilon.B represented by an edge .omega..sub.ab.epsilon.E. On the graph, .GAMMA.{A, B, E} this corresponds to vertices of A connected to vertices of B with weighted edges, where the weight represents the weight of association. One may think of the association weights forming an association matrix, .OMEGA.. In the process of fusion there are commonly constraints that describe feasible joint events, i.e., each element of one set may be assigned to at most only one element of the other set and vice-versa. In such cases the joint event is properly termed a match or, defined on a bipartite graph, a bipartite match. If this match has maximum cardinality, generally corresponding to the constraint that a feasible joint event is a one-to-one mapping (always possible with false alarms), then it is called a perfect match.
In general the representation of objects is a multidimensional state value with an associated error estimate. Commonly the state value is an estimated mean value and the error is represented as an associated covariance matrix defining a Gaussian probability distribution. When a probabilistic interpretation is given to the association weights, as we have assumed, the merging may be done in a variety of ways that have particular probabalistic interpretations. The nearest-neighbor approach, where the largest association weight at each node of one set alone determines the assignment, essentially assumes that there is virtually only one individual pairwise association of importance for every element, a condition of sparsity of the association matrix, .OMEGA.. The nearest-neighbor approach is the simplest of greedy heuristics. The optimum weighted bipartite match corresponds to the most probable, or modal, joint event, and is also used as a fusion method.
In dense environments where individual elements appear to have many significant associations, a more appropriate approach to this data association problem is described by Bar-Shalom (Tracking and Data Association, ACADEMIC PRESS (1968)) and is referred to as JPDA (joint probabilistic data association). In this approach each association weight is taken as an individual pairwise association probability or marginal association probability. The relative probability of one match with respect to any other is taken as the product of the individual pairwise association probabilities (the edge weights) of the match. (Since objective functions are usually summed, this corresponds to the sum over the log of the pairwise association probabilities). The expected probability that a and b refer to the same object is determined by summing the joint probabilities of the perfect matches in which a and b are paired and normalizing by the sum of joint probabilities over all possible perfect matches. For an N.times.N association matrix, .OMEGA., this may be alternatively stated as EQU &lt;p.sub.ab &gt;=.OMEGA..sub.ij *perM.sub.(i,j) /per.OMEGA. (1)
where the permanent of .OMEGA.is defined as ##EQU1##
which is similar to the definition of the determinant with the exception that the absolute value of the Levi-Civita symbol is used to represent the sum over all permutations, .sigma., of the indices 1 . . . N and the permanent--minor, or perM.sub.(i,j), is determined by taking the permanent of the matrix M.sub.(i,j), generated by crossing out the ith row and jth column of the matrix .OMEGA..
Valiant (The Complexity of Computing the Permanent, THEORETICAL COMPUTER SCIENCE, 8, 189-201 (1979)) has shown that the evaluation of the permanent of a 0-1 matrix (similar to the validation matrix for JPDA), equivalent to counting the number of perfect matches, is NP-hard. Complete evaluation of the permanent of a general association matrix is equivalent to enumeration of all possible perfect matches, a significantly more difficult problem. This implies that the exact solution of the JPDA is indeed NP-hard. Approximation methods, however, do exist and generally reduce the computational scaling significantly. These methods themselves then become the important subjects of consideration in terms of computational scaling.
Determining computational tractability in approaches to tracking for large-scale real-time problems is an exercise of putting practical upper bounds on algorithmic scaling. Clearly, any algorithm will scale at least linearly with the size of the input data. We would maintain, perhaps arbitrarily, that for large-scale problems quadratic algorithmic scaling forms a practical upper bound.
Thresholding the elements of .OMEGA. is one approach that reduces the scaling of JPDA (or any other approach). The permanent may be evaluated recursively via a development through permanent-minors in the same manner as a determinant is evaluated by a Laplacian development through minors. For sparse matrices with O(kN) elements this evaluation method appears to scale at worst as N.sup.k. Clearly, by thresholding matrix elements to guarantee sparsity, one may both approximate the permanent and put a limit on the scaling behavior of the evaluation algorithm.
Gating is the general problem in data fusion of determining significant association probabilities between two large sets of linear, multidimensional pattern elements (see S. S. Bleckman, Multi-Target Tracking with Radar Applications (Artech House 1986)), e.g., thresholding the association probability overlap integrals between a set of measured state vectors and a set of of estimated state vectors, both having associated error distributions. As a precursorial coarse assignment method for multitarget tracking, it reduces the computational complexity of the NP-hard exact JPDA, or any other data association method.
Computing the full association matrix between two large data sets of size N scales as N.sup.2 in time. Also, computing the association probability overlap integral between two errored vectors is generally a computationally expensive procedure. For sparse systems, those where there are only order N significant associations, where significance is determined by a "gate ", this becomes a problem since a lot of work is performed relative to the significant pieces of information garnered. Two outstanding problems are determining a good or optimally scaling association algorithm and a method of evaluation that computes a minimum number of associations that are likely to satisfy the gating criterion. Solution of these problems contributes important computational labor savings to many data association tasks.
An association probability is essentially the probability overlap integral between two (distributed) states. Significant associations exist, roughly speaking, for near-neighbors in state space. If a probability distribution for a state is not local, e.g., cannot be bounded to a small, connected and convex volume of the state space, then it will generally be necessary to evaluate a large number of overlap integrals and consideration of efficiently scaling algorithms may not be worthwhile. On the other hand, if the probability distributions do have these geometric properties, then preprocessing of the distributed states and the application of an efficiently scaling multidimensional search tree algorithm can significantly improve gating efficiency.
In order to eliminate the need to individually consider every pairwise association it is necessary to determine if the thresholding imposed by the gating criterion on the pairwise associations of errored vectors induces or can be decomposed to a thresholding criterion on the individual distributed states themselves. If a thresholding criteria can be so determined so as to define finite volumes in state space for each state, then the existence of a significant association implies the geometric intersection of these volumes (or at least we can so define the induced thresholding criterion). The determination of the intersections of finite geometric objects can be done efficiently by the use of data structures known as multidimensional search trees (see Valiant and Blackman, supra).